package com.sicheng.lc.周赛.分类.贪心.区间问题;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/31 20:57
 */
public class 最大不相交区间数量 {
    //https://www.acwing.com/problem/content/description/910/
    /**
     * 给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
     *
     * 输出可选取区间的最大数量。
     *
     * 输入格式
     * 第一行包含整数 N，表示区间数。
     *
     * 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
     *
     * 输出格式
     * 输出一个整数，表示可选取区间的最大数量。
     *
     * 数据范围
     * 1≤N≤10^5,
     * −10^9≤ai≤bi≤10^9
     * 输入样例：
     * 3
     * -1 1
     * 2 4
     * 3 5
     * 输出样例：
     * 2
     */

    // 和区间选点一模一样 思路代码都没变
    // 贪心正确性的核心就是证明
    //   1.贪心解 <= 最优解  =====>这个是一定对的，贪心解是所有合法解中较优的，最优解是所有合法解中最优的
    //   2.贪心解 >= 最优解  =====>我们证明这个就行（一般结合实际题目来反证，我们假设贪心解 < 最优解 有无冲突即可）
    //   只要能做到2 最终 贪心解==最优解 那么这个贪心才是正确的
}
